import math
import random

def assign_cluster(x, centers):
    """
    将样本x分配到最近的聚类中心
    参数:
        x: 单个样本（列表/元组，如[1,2,3]）
        centers: 聚类中心列表（每个元素为样本格式）
    返回:
        最近聚类中心的索引（整数）
    """
    min_distance = float('inf')  # 初始化最小距离为无穷大
    best_cluster = 0             # 初始化最佳聚类索引
    
    for i, center in enumerate(centers):
        # 计算欧氏距离：sqrt(sum((x_i - c_i)^2))
        distance = math.sqrt(sum((a - b)** 2 for a, b in zip(x, center)))
        
        # 更新最小距离和最佳聚类
        if distance < min_distance:
            min_distance = distance
            best_cluster = i
    
    return best_cluster

def Kmeans(data, k, epsilon=1e-5, iteration=100):
    """
    K均值聚类主函数
    参数:
        data: 样本集（列表，每个元素为样本）
        k: 聚类数量（正整数）
        epsilon: 收敛阈值（中心变化小于该值则停止，默认1e-5）
        iteration: 最大迭代次数（默认100）
    返回:
        centers: 最终聚类中心列表
        labels: 每个样本的聚类标签列表（与data顺序对应）
    """
    # 输入合法性校验
    if not data:
        raise ValueError("输入数据不能为空")
    if k <= 0 or k > len(data):
        raise ValueError(f"k值必须为(0, {len(data)}]之间的整数")
    if iteration <= 0:
        raise ValueError("迭代次数必须为正整数")
    
    # 初始化聚类中心：从数据中随机选择k个样本
    centers = random.sample(data, k)
    n_features = len(data[0])  # 特征维度
    
    for _ in range(iteration):
        # 1. 分配阶段：将所有样本分配到最近的聚类中心
        clusters = [[] for _ in range(k)]  # 存储每个聚类的样本
        for sample in data:
            cluster_idx = assign_cluster(sample, centers)
            clusters[cluster_idx].append(sample)
        
        # 2. 更新阶段：计算新的聚类中心（均值）
        new_centers = []
        for cluster in clusters:
            if not cluster:  # 处理空聚类（重新随机选一个样本）
                new_center = random.choice(data)
            else:
                # 按特征维度计算均值（zip(*cluster)将样本按特征维度分组）
                new_center = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            new_centers.append(new_center)
        
        # 3. 收敛检查：计算新旧中心的最大距离
        max_change = 0.0
        for old, new in zip(centers, new_centers):
            change = math.sqrt(sum((a - b)** 2 for a, b in zip(old, new)))
            if change > max_change:
                max_change = change
        
        # 如果中心变化小于阈值，提前停止迭代
        if max_change < epsilon:
            centers = new_centers
            break
        
        centers = new_centers  # 更新中心继续迭代
    
    # 生成最终的样本标签
    labels = [assign_cluster(sample, centers) for sample in data]
    return centers, labels